다항 시간

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 다항 시간 알고리즘 (Polynomial Time Algorithm)
- 2.2. 복잡도 클래스 P (Complexity Class P)
3. 다항 시간의 종류
참조

1. 개요

다항 시간은 알고리즘의 실행 시간을 특징짓는 개념으로, 입력 크기에 대한 실행 시간의 증가율이 다항식으로 표현될 수 있는 알고리즘을 의미한다. 어떤 다항식 l(k)가 존재하여, 임의의 k 비트 데이터 x에 대해 알고리즘 A에 x를 입력했을 때 A가 멈출 때까지의 단계 수가 l(k) 이하일 경우, A는 다항 시간 알고리즘으로 간주된다. 결정적 알고리즘과 확률적 알고리즘 모두 다항 시간 알고리즘으로 인정될 수 있으며, 결정적 다항 시간 알고리즘으로 풀 수 있는 판정 문제의 집합을 클래스 P라고 한다. 다항 시간의 종류에는 선형 시간, 제곱 시간, 세제곱 시간 등이 있다.

더 읽어볼만한 페이지

계산 복잡도 이론 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
계산 복잡도 이론 - 선형 시간
선형 시간은 알고리즘의 실행 시간이 입력 크기에 비례하여 증가하는 것을 의미하며, O(n)의 시간 복잡도를 가지는 알고리즘 분석의 중요한 척도로 활용된다.

다항 시간

2. 정의

어떤 문제를 해결하는 데 걸리는 시간이 입력 크기의 다항식으로 표현되는 알고리즘을 '''다항 시간 알고리즘'''이라고 한다. 결정적 알고리즘뿐만 아니라 확률적 알고리즘도 포함될 수 있다. 다항 시간 알고리즘으로 풀 수 있는 판정 문제의 집합을 복잡도 클래스 P라고 부른다.

2. 1. 다항 시간 알고리즘 (Polynomial Time Algorithm)

어떤 다항식 l(k)가 존재하여, 임의의 k와 임의의 k 비트 데이터 x에 대해, A에 x를 입력했을 때 A가 멈출 때까지의 단계 수가 l(k) 이하일 때, 알고리즘 A를 '''다항 시간 알고리즘'''이라고 한다.

다항 시간 알고리즘은 결정적 알고리즘만을 한정하는 경우와 확률적 알고리즘도 허용하는 경우가 있다.

2. 2. 복잡도 클래스 P (Complexity Class P)

결정적 다항 시간 알고리즘(위에서 정의된)으로 풀 수 있는 '''판정 문제'''의 집합을 P라고 부른다(판정 문제 이외의 문제는 클래스 P에 포함되지 않음에 주의).

3. 다항 시간의 종류

다항 시간 알고리즘의 시간 복잡도는 입력 크기 n에 대한 다항식으로 표현된다.

종류	설명
선형 시간	O(n)
제곱 시간	O(n²)
세제곱 시간	O(n³)

3. 1. 선형 시간 (Linear Time)

O(''n'')

3. 2. 제곱 시간 (Quadratic Time)

O(n²)

3. 3. 세제곱 시간 (Cubic Time)

알고리즘의 수행 시간이 입력 크기의 세제곱에 비례하여 증가한다. O(''n''³)으로 표기한다.

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com